package 动态规划.贪心算法;

import java.util.Arrays;

public class 跳跃游戏2 {
    public int jump(int[] nums) {
          int n=nums.length;
          int sum=0,jump=0,end=0;
         for (int i = 0; i < n - 1; i++) {
            sum=Math.max(sum,i+nums[i]);
            if (i==end){
                jump++;
                end=sum;
            }
        }
          return jump;
    }
    public int jump1(int[] nums) {
        // dp[i] 表示到达位置i的最小步数
        // dp[i]
        int n = nums.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp,nums.length+1);
        dp[1] = 0;
        for (int i = 2; i < n+1; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[j-1]>=i-j){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n];
    }
}
